今天的題單：

• Two sum

• Valid Parentheses

• Merge Two Sorted Lists

1. Two Sum

馬上想到的是 Brute force 解法，兩個迴圈解決，時間複雜度是 O(n^2)。
但難的是接下來的 follow up，如何降低時間複雜度？

想了 10 分鐘想不太到，看了一下 hint，提到 hash map 後靈感突然來了。
利用 hash table 時間複雜度 O(n):

• 每個 element 在 hash table 有自己的 bucket，對應的 value 是 「與 key 值相加等於 target sum 的 value」的 index (如果存在的話)

• 掃一遍 list，對於每一個 element，先查自己的 bucket 有沒有值，有就表示找到解了；若沒有，就在 key=target-element 的 bucket 放入自己的 index

給一個實例：

例如現在 target 是 9，list 裡有 2 和 7 兩個數字加起來是 9。當掃過 list 先看到 2 時，檢查 hash table 在 index 2 的位置看有沒有值，沒有的話表示在此之前沒有看到與 2 相加等於 9 的數字（也就是 7），於是在 index 7 的位置填入 2。繼續往 list 後面看到 7 時，檢查 hash table 中 index 7 的位置，此時發現裡面有值了，表示之前已經看過與 7 相加等於 target 的值（也就是 2），於是搜尋結束。

原本想用 vector 實作，index 直接當 key，結果因為會 element 有負值所以不行，轉用 map。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> hashmap;
        vector<int> ans(2);

        // map idx -> element
        // map value -> record the index of element which value is (target - idx)
        for (int i=0; i<nums.size(); i++) {
            // if (nums[i] > target) continue;
            if (hashmap.find(nums[i]) == hashmap.end()) // No record
                hashmap[target-nums[i]] = i;
            else {
                // found
                ans[0] = i;
                ans[1] = hashmap[nums[i]];
                break;
            }
        }
        return ans;
    }
};

之後又想到一個解法﹔用一個 map 記 element 跟 index 的對應，先把 input list sort 之後再對每個 element 之後的值用 binary search 找解。時間複雜度是 O(nlogn)。

20. Valid Parentheses

看到 Last in first out 性質的 task 就想到用 stack。

class Solution {
public:
    bool isValid(string s) {
        stack<char> store_stack;
        
        for (int i=0; i < s.length(); i++) {
            if (s[i] == '(')
                store_stack.push(s[i]);
            else if (s[i] == '{')
                store_stack.push(s[i]);
            else if (s[i] == '[')
                store_stack.push(s[i]);
            else {
                // if the first one is a close bracket
                if (store_stack.empty())
                    return false;
                
                if (s[i] == ')') {
                    char top = store_stack.top();
                    if (top == '(')
                        store_stack.pop();
                    else
                        return false;
                } else if (s[i] == '}') {
                    char top = store_stack.top();
                    if (top == '{')
                        store_stack.pop();
                    else
                        return false;
                } else if (s[i] == ']')  {
                    char top = store_stack.top();
                    if (top == '[')
                        store_stack.pop();
                    else
                        return false;
                }
            }
        }

        if (store_stack.empty())
            return true;
        else
            return false;
    }
};

if-else 太多寫起來太冗長，比較簡潔的寫法：

// Leetcode sample code
class Solution {
public:
    bool isValid(string s) {
        stack<int>st;
        int n = s.size();
        for(int i = 0; i < n; i++)
        {
            char c = s[i];
            if(s[i]=='(' ||s[i]=='{' || s[i]=='[')
            {
                st.push(s[i]);
            }
            else 
            {
                if (st.empty() || // if the stack is empty or 
                    (c == ')' && st.top() != '(') || // the closing bracket doesn't match the corresponding opening bracket at the top of the stack
                    (c == '}' && st.top() != '{') ||
                    (c == ']' && st.top() != '[')) {
                    return false; // the string is not valid, so return false
                }
               
                st.pop();
            }
        }
        return st.empty();
    }
};

21. Merge Two Sorted Lists

實作 Merge Sort。
題目給的兩個 list 都已經 sort 過了，所以就從兩個 list 的 head 開始一一比大小把 node 接好即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        bool list1_empty = false;
        bool list2_empty = false;

        if (list1 == nullptr) list1_empty = true;
        if (list2 == nullptr) list2_empty = true;

        // if the list are both empty
        if (list1_empty && list2_empty)
            return list1;

        // if one of the list is empty
        if (list1_empty && !list2_empty)
            return list2;
        else if (!list1_empty && list2_empty)
            return list1;

        // The other cases
        ListNode* p1 = list1;
        ListNode* p2 = list2;
        ListNode* head = nullptr;
        ListNode* cursor = nullptr;

        // the first node of the merged list
        if (p1->val <= p2->val) {
            head = cursor = p1;
            p1 = p1->next;
        }
        else {
            head = cursor = p2;
            p2 = p2->next;
        }
        
        while (p1 != nullptr && p2 != nullptr) {
            if (p1->val <= p2->val) {
                (*cursor).next = p1;
                p1 = p1->next;
            }
            else {
                (*cursor).next = p2;
                p2 = p2->next;
            }
            cursor = (*cursor).next;
        }

        if (p1 == nullptr) // end at p1
            (*cursor).next = p2;
        else
            (*cursor).next = p1;
    
        return head;

    }
};

一些感想

• 意外的第一題蠻簡單也很有趣

• 還不太習慣 leetcode 的環境介面。雖然我知道它已經 include 大部分的 standard library 和 using namespace std;，所以 STL 容器和 algorithm 裡的 function 可以直接用，但不需要自己 include 標頭檔寫起來還是感覺不太對勁… （optimization 還有開 -O2 蠻酷的）

• 有些 STL 容器的 function 太久沒用忘記了，需要多熟悉

• 犯了一些常見的錯，要看清楚題目條件，例如 element 的值域範圍